package 算法.排序;

import java.util.Arrays;

/**
 * 无序(无需或者递减) 变 有序(单调递增) 的过程中，所有需要交换的次数就是逆序对的总数。
 */
public class JZ51数组中的逆序对 {
    //前一个数大于后一个  逆序对
    //输出P mod 1000000007
    //归并排序
    /**
     * 无序(无需或者递减) 变 有序(单调递增) 的过程中，所有需要交换的次数就是逆序对的总数。
     */
    public int count = 0;
    public int mod = 1000000007;
    public int InversePairs(int [] array) {
        sort(array);
        return count ;
    }

    //归并排序
    private int[] sort(int[] nums){
        if(nums.length==1)
            return  nums;
        int mid = nums.length / 2 ;
        int[] leftNums = sort(Arrays.copyOfRange(nums,0,mid));
        int[] rightNms = sort(Arrays.copyOfRange(nums,mid,nums.length));
        return  merge(leftNums,rightNms);
    }
    //合并操作
    private int[] merge(int[] leftNums, int[] rightNums){
        int[] res = new int[leftNums.length+rightNums.length];
        int i=0,j=0,p=0;
        while (i<leftNums.length && j<rightNums.length){
            if(leftNums[i]<=rightNums[j]){
                res[p++] = leftNums[i++];
            }else{
                res[p++] = rightNums[j++];
                //左小于右  --- 产生逆序
                count += (leftNums.length -  i);
                count %= mod;
            }
        }
        while (i<leftNums.length)
            res[p++] = leftNums[i++];
        while (j<rightNums.length)
            res[p++] = rightNums[j++];
        return res;
    }


    /**
     * 暴力
     * @param array
     * @return
     */
    public int InversePairs3(int [] array) {
        long res=0;
        for(int i=0;i<array.length;i++){
            for(int j=i+1;j<array.length;j++){
                if(array[i]>array[j]){
                    res++;
                }
            }
        }
        return Math.abs((int)(res%1000000007));
    }


    //树状数组
    public int InversePairs2(int [] array) {
        int n = array.length;
        int[] temp = new int[n];
        System.arraycopy(array, 0, temp, 0, n);
        //排序得到一份有序的数组
        Arrays.sort(temp);
        //二分法重新映射，将数字变成其在有序数组中的位置
        for (int i = 0; i < n; ++i)
            //二分法查找在其在有序数组中的位置
            array[i] = Arrays.binarySearch(temp, array[i]) + 1;
        //建立大小为n的树状数组
        BIT bit = new BIT(n);
        int res = 0;
        //统计逆序对
        for(int i = 0; i < n; i++){
            //前缀和做差
            res = (res + bit.query(n) - bit.query(array[i])) % mod;
            bit.update(array[i]);
        }
        return  res;
    }

    class BIT {
        private int[] tree;
        private int n;

        //初始化树状数组的大小
        public BIT(int m) {
            this.n = m;
            this.tree = new int[m + 1];
        }

        //使数组呈现2、4、8、16这种树状
        public int lowbit(int x) {
            return x & (-x);
        }

        //查询序列1到x的前缀和
        public int query(int x) {
            int res = 0;
            while(x != 0){
                res += tree[x];
                x -= lowbit(x);
            }
            return res;
        }

        //序列x位置的数加1
        public void update(int x) {
            while(x <= n){
                tree[x]++;
                x += lowbit(x);
            }
        }
    }
}
